# 链表的中间结点： https://leetcode-cn.com/problems/middle-of-the-linked-list/submissions/

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        """
            可以使用快慢指针解决，low指针一次移动一次， high指针还有fast次移动两次
            分情况：
            1. 为奇数个数时， 恰好fast指针走到最后元素，返回low指针
            2. 为偶数时， fast 走不到最后一个元素，结束， 返回 low下一个元素

            不同点在于， 当为偶数时，fast停在 倒数第二个元素， 此时返回 low.next，
            当为奇数时， fast停在链表最后的位置， 此时返回 low
        """
        low = fast = head
        # 这里需要加上 fast.next 的原因是，当 fast是最后的位置 fast.next已经是 None了，没有 .next属性了
        while fast.next and fast.next.next:
            low = low.next
            fast = fast.next.next

        return low.next if fast.next else low



# 官网的想法更简单
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

